package revise;

//                                          模拟实现链表


//链表的每个节点
class Node {
    public String val;
    public Node next = null;
    public Node(String val){
        this.val = val;
    }
}
public class MyLinkedList {
    //head 指向第一个节点
    public Node head = null;

    //头插
    public void addFirst(String val){
        Node newNode = new Node(val);
        newNode.next = head;
        head = newNode;
    }
    public void addLast(String val){
        //特殊情况
        if (head == null){
            Node newNode = new Node(val);
            head = newNode;
            return;
        }
        //找到最后一个节点
        Node cur = head;
        while (cur.next != null){
            cur = cur.next;
        }
        //此时 cur 就指向链表的最后一个节点
        Node newNode = new Node(val);
        cur.next = newNode;
    }
    public void add(int index, String val){
        //判断下标合法性
        if (index < 0 || index > size()){
            throw new IndexOutOfBoundsException("下标超出异常");
        }
        //特殊情况
        if (index == 0){
            addFirst(val);
            return;
        }
        //找到下标为 index - 1 的位置
        int i = 0;
        Node prve = head;
        for (i = 0; i < index - 1; i++){
            prve = prve.next;
        }
        Node newNode = new Node(val);
        newNode.next = prve.next;
        prve.next = newNode;
    }
    //按照下标删除
    public String remove(int index){
        //判断下标合法性
        if (index < 0 || index >= size()){
            throw new IndexOutOfBoundsException("下标超出异常");
        }
        //特殊情况
        if (index == 0){
            String elem = head.val;
            head = head.next;
            return elem;
        }
        Node prve = head;
        for (int i = 0; i < index - 1; i++){
            prve = prve.next;
        }
        String elem = prve.next.val;
        Node toRemove = prve.next;
        prve.next = toRemove.next;
        return elem;
    }
    //按照值来删除
    public int remove(String val){
        //特殊情况
        if (head.val.equals(val)){
            head = head.next;
            return 0;
        }
        //找到要删除元素的前一个节点
        int index = 1;
        Node prve = head;
        for (prve = head; prve.next != null; prve = prve.next){
            if (prve.next.val.equals(val)){
                break;
            }
            index++;
        }
        if (prve.next == null){
            return -1;
        }
        //删除操作
        Node toRemove = prve.next;
        prve.next = toRemove.next;
        return index;
    }

    public int size(){
        int size = 0;
        for (Node cur = head; cur != null; cur = cur.next){
            size++;
        }
        return size;
    }
    public String toString(){
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append("[");
        for (Node cur = head; cur != null; cur = cur.next){
            stringBuilder.append(cur.val);
            if (cur.next != null){
                stringBuilder.append(", ");
            }
        }
        stringBuilder.append("]");
        return stringBuilder.toString();
    }
}
